1. Field of the Invention
The present invention relates to wireless localization and communications technology. More particularly, the present invention relates to estimating a mobile terminal's position using a time-of-arrival (TOA) technique in the presence of non-line-of-sight (NLOS) conditions.
2. Discussion of the Related Art
Because of its very wide bandwidth, ultra-wideband (UWB) technology promises accurate ranging and localization systems capable of resolving individual multipath components (MPCs). Using UWB technology, the time-of-arrival (TOA) of the received signal can be estimated with high accuracy when the first arriving path is correctly identified. Various systems using UWB technology have been disclosed, including those disclosed in the articles: (a) “Analysis of undetected direct path in time of arrival based UWB indoor geolocation,” by B. Alavi and K. Pahlavan, published in Proc. IEEE Vehic. Technol. Conf. (VTC), vol. 4, Dallas, Tex., September 2005, pp. 2627-2631; (b) “Non-coherent TOA estimation in IR-UWB systems with different signal waveforms,” by I. Guvenc, Z. Sahinoglu, A. F. Molisch, and P. Orlik, published in in Proc. IEEE Int. Workshop on Ultrawideband Networks (UWBNETS), Boston, Mass., October 2005, pp. 245-251, (invited paper); (c) “Analysis of threshold-based TOA estimators in UWB channels,” by D. Dardari, C. C. Chong, and M. Z. Win, published in the 14th European Signal Processing Conference (EUSIPCO 2006), Florence, Italy, September 2006, (Invited Paper); and (d) “Improved lower bounds on time of arrival estimation error in UWB realistic channels,” by D. Dardari, C. C. Chong and M. Z. Win, published in IEEE Intl. Conf. on Ultra-Wideband (ICUWB 2006), Waltham, Mass., USA, September 2006 (Invited Paper).
One challenge for a localization system is to successfully mitigate NLOS effects. When the direct path between an anchor node (AN) and the mobile terminal is obstructed, the TOA of the signal to the AN is delayed, which introduces a positive bias. An NLOS TOA estimate adversely affects localization accuracy. Hence, prior art cellular networks typically identify ANs under NLOS conditions and mitigate their effects. For example, the article “The non-line of sight problem in mobile location estimation,” by M. P. Wylie and J. Holtzman, published in Proc. IEEE Int. Conf. Universal Personal Commun., Cambridge, Mass., September 1996, pp. 827-831, teaches comparing a standard deviation of range measurements with a threshold for NLOS signal identification, when the measurement noise variance is known. Similarly, the article “Decision theoretic framework for NLOS identification,” by J. Borras, P. Hatrack, and N. B. Mandayam, “published in Proc. IEEE Vehicular Technol. Conf. (VTC), vol. 2, Ontario, Canada, May 1998, pp. 1583-1587, discloses a decision-theoretic NLOS identification framework using various hypothesis tests for known and unknown probability density functions (PDFs) of the TOA measurements.
The article “Non-parametric non-line-of-sight identification,” by S. Gezici, H. Kobayashi, and H. V. Poor, published in Proc. IEEE Vehic. Technol. Conf. (VTC), vol. 4, Orlando, Fla., October 2003, pp. 2544-2548, discloses a non-parametric NLOS identification approach, which allows the PDFs of the TOA (i.e., distance) measurements to be approximated. A suitable distance metric is used between the known measurement noise distribution and the non-parametrically estimated measurement distribution.
The above NLOS identification techniques all assume that the TOA measurements for NLOS base stations (BSs) change over time, which is reasonable for a moving terminal. For a moving terminal, the TOA measurements have a larger variance. However, when the terminal is static (e.g., in wireless personal area network (WPAN) applications), the distribution of the NLOS measurements may show little deviation from the distribution under LOS condition. There, the multipath characteristics of the received signal provide insight useful for LOS/NLOS identification. For example, European Patent Application Publication EP 1,469,685, entitled “A method distinguishing line of sight (LOS) from non-line-of-sight (NLOS) in CDMA mobile communication system,” by X. Diao and F. Guo, filed on Mar. 29, 2003, published on Oct. 20, 2004, discloses that a received code division multiple access (CDMA) signal is LOS if: 1) the power ratio of the global maximum path to the local maximum path is greater than a given threshold, and 2) the arrival time difference between the first path and the maximum path is less than a given time interval. Similarly, the article “ML time-of-arrival estimation based on low complexity UWB energy detection,” by Rabbachin, I. Oppermann, and B. Denis, published in Proc. IEEE Int. Conf. Ultrawideband (ICUWB), Waltham, Mass., September 2006, discloses that the NLOS identification for UWB systems may be performed by comparing the normalized strongest path with a fixed threshold. In either scheme, judicious parameter selection (e.g., the threshold or the time interval) is essential.
As an alternative to identifying NLOS conditions from the received multipath signal, information derived from the overall mobile network may be used to mitigate NLOS conditions. For example, the article “A non-line-of-sight error mitigation algorithm in location estimation,” by P. C. Chen, published in Proc. IEEE Int. Conf. Wireless Commun. Networking (WCNC), vol. 1, New Orleans, La., September 1999, pp. 316-320, discloses a residual-based algorithm for NLOS mitigation. That algorithm is based on three or more available BSs, using location estimates and residuals for different combinations of BSs. (When all the nodes are LOS, three BSs are required to perform a two-dimensional (2-D) localization, while four BSs are required to perform a 3-dimensional (3-D) localization.) The location estimates with smaller residuals are more likely to represent the correct terminal location. Hence, the technique disclosed in the article weights the different location estimates inversely with the corresponding residuals.
Other NLOS mitigation techniques using information derived from the mobile network are disclosed in (a) “Robust estimator for non-line-of-sight error mitigation in indoor localization,” by R. Casas, A. Marco, J. J. Guerrero, and J. Falco, published in Eurasip J. Applied Sig. Processing, pp. 1-8, 2006; (b) “Time-of-arrival based localization under NLOS conditions,” by Y. T. Chan, W. Y. Tsui, H. C. So, and P. C. Ching, published in IEEE Trans. Vehic. Technol., vol. 55, no. 1, pp. 17-24, January 2006; (c) “A database method to mitigate the NLOS error in mobile phone positioning,” by B. Li, A. G. Dempster, and C. Rizos, published in Proc. IEEE Position Location and Navigation Symposium (PLANS), San Diego, Calif., April 2006; (d) “An iterative NLOS mitigation algorithm for location estimation in sensor networks,” by X. Li, published in Proc. IST Mobile and Wireless Commun. Summit, Myconos, Greece, June 2006; (e) “Non-line-of-sight error mitigation in mobile location,” by L. Cong and W. Zhuang, published in Proc. IEEE INFOCOM, Hong Kong, March 2004, pp. 650-659; (f) “A non-line-of-sight mitigation technique based on ML-detection,” by J. Riba and A. Urruela, published in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing (ICASSP), vol. 2, Quebec, Canada, May 2004, pp. 153-156; (g) “A linear programming approach to NLOS error mitigation in sensor networks,” by S. Venkatesh and R. M. Buehrer, published in Proc. IEEE IPSN, Nashville, Tenn., April 2006; (h) “An efficient geometry-constrained location estimation algorithm for NLOS environments,” by C. L. Chen and K. T. Feng, published in Proc. IEEE Int. Conf. Wireless Networks, Commun., Mobile Computing, Hawaii, USA, June 2005, pp. 244-249; and (i) “A TOA based location algorithm reducing the errors due to non-line-of-sight (NLOS) propagation,” by X. Wang, Z. Wang, and B. O. Dea, published in IEEE Trans. Vehic. Technol., vol. 52, no. 1, pp. 112-116, January 2003.
Some of the prior localization algorithms assign equal reliabilities to each BS, thus these localization algorithms do not take into account NLOS conditions. As a result, the presence of NLOS BSs degrades localization accuracy in these algorithms significantly.
The prior art also includes many weighted least-squares approaches for estimating a mobile terminal position. Typically, in these approaches, the weight for the signal received from each BS is derived from a measurement variance (see, e.g., the articles by M. P. Wylie et al., J. Borras et al., and S. Gezici et al., discussed above). The approaches rely on the fact that, under an NLOS condition, the measurements related to a moving terminal show a large variance. However, such approaches do not reliably provide accurate information regarding NLOS BSs.
Weighted least-squares techniques based on measurement variances typically require a large number of observations. Large memory is therefore required to store the measured distances and the delays that are necessary for estimating a mobile terminal's location.